package com.zyk.leetcode;

import java.util.ArrayDeque;

/**
 *
 * 二叉搜索树的序列化与反序列化
 *
 * @author zhangsan
 * @date 2021/3/31 17:22
 */
public class C449 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = postorder(root, new StringBuilder());
        if (sb.length() > 0)
            sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public StringBuilder postorder(TreeNode root, StringBuilder sb) {
        if (root == null)
            return sb;
        postorder(root.left, sb);
        postorder(root.right, sb);
        sb.append(root.val);
        sb.append(' ');
        return sb;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty())
            return null;
        ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
        for (String s : data.split("\\s+"))
            nums.add(Integer.valueOf(s));
        return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
    }


    public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
        if (nums.isEmpty())
            return null;
        int val = nums.getLast();
        if (val < lower || val > upper)
            return null;

        nums.removeLast();
        TreeNode root = new TreeNode(val);
        root.right = helper(val, upper, nums);
        root.left = helper(lower, val, nums);
        return root;
    }

}

class TestC110 {

    public static void prePrint(TreeNode node) {
        if(node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prePrint(node.left);
        prePrint(node.right);
    }

    // for test
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(9);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(10);

        prePrint(root);
        System.out.println();


        C449 c449 = new C449();
        String s = c449.serialize(root);
        System.out.println(s);


        TreeNode head = c449.deserialize(s);
        prePrint(head);
    }
}
